﻿// Write a program that finds the sequence of maximal sum in given array. Example:
//	{2, 3, -6, -1, 2, -1, 6, 4, -8, 8} -> {2, -1, 6, 4}
//	Can you do it with only one loop (with single scan through the elements of the array)?

using System;

class SequenceWithMaxSum
{
    static void Main()
    {
        // get the length of the array
        Console.Write("Enter length of the array : ");
        string length = Console.ReadLine();
        int lengthOfArray;
        while (!int.TryParse(length, out lengthOfArray))
        {
            Console.Write("Invalid input. Enter again length for the array : ");
            length = Console.ReadLine();
        }

        decimal[] array = new decimal[lengthOfArray];

        for (int index = 0; index < lengthOfArray; index++)
        {
            // get the element of the array
            Console.Write("Enter element of the array : ");
            string element = Console.ReadLine();
            decimal elementOfArray;
            while (!decimal.TryParse(element, out elementOfArray))
            {
                Console.Write("Invalid input. Enter element again : ");
                element = Console.ReadLine();
            }
            array[index] = elementOfArray;
        }

        decimal maxTemp = decimal.MinValue;
        decimal maxEnd = 0;
        int start = 0;
        int startTemp = 0;
        int end = 0;

        for (int i = 0; i < lengthOfArray; i++)
        {
            maxEnd += array[i];

            if (array[i] > maxEnd)
            {
                maxEnd = array[i];
                startTemp = i;
            }
            if (maxEnd > maxTemp)
            {
                maxTemp = maxEnd;
                start = startTemp;
                end = i;
            }
        }

        // print the sum
        Console.WriteLine("The sum is : " + maxEnd);
        // print the sequence array
        string resultString = "";
        for (int i = start; i <= end; i++)
        {
            // for the last element of the sequence don't put comma after the element
            if (i == end)
            {
                resultString = resultString + array[i];
            }
            else
            {
                resultString = resultString + array[i] + ", ";
            }
        }
        Console.WriteLine("And the sequence with max sum is : {" + resultString + "}");
    }
}